1. Field of the Invention
This invention relates to the field of data processing. More particularly, this invention relates to data processing systems that incorporate special purpose circuits for performing division and/or square root operations.
2. Description of the Prior Art
It is known to provide special purpose division and/or square root performing circuits that operate upon an iterative basis. Examples of such systems are described in U.S. Pat. No. 4,939,686; "Algorithm for High Speed Shared Radix 4 Division and Radix 4 Square Root" by Jan Fandrianto, pages 73 to 79 of Proceeding of 8th Symposium on Computer Arithmetic, May 19-21 1987, Villa Olmo, Como, Italy; and "Radix-4 Square Root Without Initial PLA" by Milos D Ercegovac and Tomas Lang, pages 162 to 168 of Proceeding of 9th Symposium on Computer Arithmetic, Sep. 6-8 1989, Santa Monica, Calif., United States of America. These documents are incorporated herein by reference.
An example of an iterative division circuit is shown in FIG. 1 of the accompanying drawings. In this example, at initialisation the dividend A is loaded into a save register 2. A carry register 4 is initialised to a value of zero. The divisor D is loaded into a divisor register 6. A carry propagate adder 8 serves to calculate the most significant 8 bits of the sum of the values stored within the save register 2 and the carry register 4. These 8 bits represent an estimate of the partial remainder P.sub.j (at initialization this is the dividend A) and are converted to a 4 bit magnitude and a 1 bit sign in a converter 9. The 4 bit magnitude is used as one input to a quotient bit look-up table 10. The 1 bit sign is one input to a multiplexer 14. Another input to the quotient bit look-up table 10 is the most significant 4 bits (excluding any sign or hidden bits) of divisor D from the divisor register 6.
The two inputs to the quotient bit look-up table 10 together point to a 2 bit quotient digit value q.sub.j+1 that is supplied to a quotient assembly circuit 12 and a multiplexer 14. The 2 bit quotient digit value q.sub.j+1 along with the 1 bit sign output from the converter 9 indicate how many times the divisor D subject to the radix in use (in this example r is 4) can be added to four times the partial remainder P.sub.j (denoted by 4*P.sub.js, 4*P.sub.jc) such that the result remains within a restricted range dependent upon the radix r and the redundancy choosen (in this example 2/3). The quotient digit value q.sub.j+1 thus represents in redundent form (indirectly) two bits of the desired quotient result Q at the current bit position within the iterative operation. Having determined from the look-up table 10 the number of times the divisor D goes into the current partial remainder P.sub.j, a new partial remainder P.sub.j+1 must be calculated for use in subsequent iterative cycles. This may achieved by subtracting either 0, .+-. one times the divisor D or .+-. two times the divisor D from four times the current partial remainder P.sub.j. One of these five possible values to add to the partial remainder P.sub.j is selected by the multiplexer 14 in dependence upon the quotient digit value q.sub.j+1 and the sign bit and supplied to a carry save adder 16 together with a carry save representation of the current partial remainder (P.sub.jc, P.sub.js) from the sum register 2 and the carry register 4. The output from the carry save adder 16 is the new partial remainder P.sub.j+1 (which in carry save form is P.sub.j+1c, P.sub.j+1s) that is saved back into the save register 2 and the carry register 4. The process then continues to calculate the next two bits of the quotient result until the entire quotient result has been assembled and is ready for output as a full quotient value Q.
It will be appreciated that the operation of the circuit illustrated in FIG. 1 is similar to the manner in which a person would perform a manual long division using pencil and paper, i.e. at each stage determining how many times the divisor goes into the current remainder, using that number as a digit of the quotient being calculated and then subtracting that number multiplied by the divisor from the partial remainder to produce a new partial remainder.
The critical path through the circuit of FIG. 1 is marked by the thick signal lines shown. More particularly, the critical path is through the save and carry registers 2, 4, the carry propagate adder 8, the converter 9, the quotient bit look-up table 10, the multiplexer 14, the carry save adder 16 and back to the save and carry registers 2, 4. This critical path determines how quickly the circuit can operate to calculate each two bits of the desired quotient result Q. If 56 bits of quotient are required for the fill quotient result Q, then it will be necessary for the circuit of FIG. 1 to iterate 28 times with this critical path being passed through 28 times.